<<<<<<< HEAD
package leetcode2;

import java.util.*;

public class LeetCodeMain127 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if (nums==null||nums.length<3){
            return res;
        }
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                break;
            }
            int one=nums[i];
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            Set<Integer> set=new HashSet<>();
            for (int j = i+1; j < n; j++) {
                int three=nums[j];
                int tow=-(one+three);
                if (set.contains(tow)){
                    res.add(new ArrayList<>(Arrays.asList(one,tow,three)));
                    while (j<n-1&&nums[j]==nums[j+1]){
                        j++;
                    }
                }
                set.add(three);
            }
        }
        return res;
    }
    //回溯超时
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> threeSum1(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag=new boolean[nums.length];
        back(nums,0,0,flag);
        return res;
    }
    public void back(int[] nums,int startIndex,int sum,boolean[] flag){
        if (list.size()==3&&sum==0){
            Collections.sort(list);
            if (!res.contains(list)){
                res.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            flag[i]=true;
            sum+=nums[i];
            list.add(nums[i]);
            back(nums, i+1, sum, flag);
            flag[i]=false;
            sum-=nums[i];
            list.remove(list.size()-1);
        }
    }
}
=======
package leetcode2;

import java.util.*;

public class LeetCodeMain127 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if (nums==null||nums.length<3){
            return res;
        }
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                break;
            }
            int one=nums[i];
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            Set<Integer> set=new HashSet<>();
            for (int j = i+1; j < n; j++) {
                int three=nums[j];
                int tow=-(one+three);
                if (set.contains(tow)){
                    res.add(new ArrayList<>(Arrays.asList(one,tow,three)));
                    while (j<n-1&&nums[j]==nums[j+1]){
                        j++;
                    }
                }
                set.add(three);
            }
        }
        return res;
    }
    //回溯超时
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> threeSum1(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag=new boolean[nums.length];
        back(nums,0,0,flag);
        return res;
    }
    public void back(int[] nums,int startIndex,int sum,boolean[] flag){
        if (list.size()==3&&sum==0){
            Collections.sort(list);
            if (!res.contains(list)){
                res.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            flag[i]=true;
            sum+=nums[i];
            list.add(nums[i]);
            back(nums, i+1, sum, flag);
            flag[i]=false;
            sum-=nums[i];
            list.remove(list.size()-1);
        }
    }
}
>>>>>>> e5346752b4e21187c31af6aa8892a487a62be41e
